/**
 * 
 */
package com.gwcloud.leetcode.hot100;

/**
 * @ClassName   : Leetcode0072 
 * @author      : ganwei 
 * @date        : 2020年5月15日
 * @Description : Leetcode0072 编辑距离
 */
public class Leetcode0072 {
    /**
     * -解题思路，动态规划
     */
	public int minDistance(String word1, String word2) {
		int m = word1.length(), n = word2.length();
		int[][] dp = new int[m+1][n+1];
		//base case
		for(int i = 0; i <= m; i++){
			dp[i][0] = i;
		}
		for(int j = 0; j <= n; j++){
			dp[0][j] = j;
		}
		//自底向上求解
		for(int i=1; i <= m; i++){
			for(int j=1; j<=n; j++){
				if(word1.charAt(i-1) == word2.charAt(j-1)){
					dp[i][j] = dp[i-1][j-1];
				}else{
					dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1);
				}
			}
		}
		
    	return dp[m][n];
    }
	
	public int min(int a,int b,int c){
		return Math.min(a, Math.min(b, c));
	}
	
	/**
	 * -主函数
	 */
	public static void main(String[] args){
		
	}
}
